package com.peng.leetcode.backtracking;

/**
 * Solve
 *
 * @author: lupeng6
 * @create: 2020/12/29 14:42
 */
public class Solve {

    public static void main(String[] args) {
        char[][] board = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X'}
        };
        new Solve().solve(board);
        for (char[] chars : board) {
            for (char aChar : chars) {
                System.out.print(aChar);
            }
            System.out.println();
        }
    }

    private boolean[][] visited;

    private int[][] operations = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public void solve(char[][] board) {
        if (board.length == 0) {
            return;
        }
        this.visited = new boolean[board.length][board[0].length];
        int minX = 0;
        int maxX = board.length - 1;
        int minY = 0;
        int maxY = board[0].length - 1;
        for (int i = 0; i < board.length; i++) {
            dfs(board, i, minY);
            dfs(board, i, maxY);
        }
        for (int i = 0; i < board[minX].length; i++) {
            dfs(board, minX, i);
            dfs(board, maxX, i);
        }
        fill(board);
    }

    public void dfs(char[][] board, int x, int y) {
        if (board[x][y] != 'O') {
            return;
        }
        if (visited[x][y]) {
            return;
        }
        visited[x][y] = true;
        for (int[] operation : operations) {
            int newX = x + operation[0];
            int newY = y + operation[1];
            if (isArea(board, newX, newY) && !visited[newX][newY]) {
                dfs(board, newX, newY);
            }
        }
    }

    private boolean isArea(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

    private void fill(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            char[] chars = board[i];
            for (int j = 0; j < chars.length; j++) {
                if (chars[j] == 'O' && !visited[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }
}
